#include<time.h>
#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>

void swap(int *i, int *j) 
{
   *i = *i ^ *j;
   *j = *i ^ *j;
   *i = *i ^ *j;

   return;
}
//for test
int comp(const void*a,const void*b)//用来做比较的函数，从小到大。
{
    return *(int*)a-*(int*)b;
}
// 由于c语言qsort是不稳定的排序,当需要稳定排序是可使用结构体
int comp1(const void *a, const void* b)
{
    if (*(int*)(a.x)=*(int*)(b.x))
         return *(int*)(a.y)-*(int*)(b.y)
    else return *(int*)(a.x)-*(int*)(b.x)
}
// qsort(a,n,sizeof(int),comp);//调用qsort排序, n数组长度
//for test
int * generate_random_array(int max_size, int max_value, int *real_length) 
{
        srand((unsigned)time(NULL));
        int length = rand() % (max_size + 1); //生成0~maxSize+1的随机数
        *real_length = length; //这个长度的单位时int型， 
        int *arr = (int*)malloc(length * sizeof(int));  
        for (int i = 0; i < length; i++) {
            arr[i] = (rand() % (max_value + 1)) - (rand() % max_value);
        }
        return arr;
}
//for test
int* copy_array(int arr[], int length) 
{
        if (length == 0) {
            return NULL;
        }
        int *res = (int *)malloc(length * sizeof(int));
        for (int i = 0; i < length; i++) {
            res[i] = arr[i];
        }
        return res;
}
//for test
bool is_equal(int arr1[], int length1, int arr2[], int length2) 
{
    if ((length1 == 0 && length2 != 0) || (length1 != 0 && length2 == 0)) {
        return false;
    }
    if (length1 == 0 && length2 == 0) {
        return true;
    }
    if (length1 != length2) {
        return false;
    }
    for (int i = 0; i < length1; i++) {
        if (arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}
//for test
void print_array(int arr[], int length) {
    if (length == 0) {
        return;
    }
    for (int i = 0; i < length; i++) {
        printf("%d  ", arr[i]);
    }
    printf("\n");
}

void insert_sort (int arr[], int length) 
{
    if (arr == NULL || length < 2) return;  // 小于一个元素不排序

    for (int i = 1 ; i < length;  i++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) { //从后往前插入
                swap(&arr[j], &arr[j - 1]);
        }
    }
    return;
}

void main(int argc, char **argv) {
    int test_time = 500000;
    int max_size = 100;
    int max_value = 100;
    bool succeed = true;
    int *arr1 = NULL;
    int *arr2 = NULL;
    int *arr3 = NULL;
    int real_length = 0; //sizeof 不能通过指针来计算数组的长度
    for (int i = 0; i < test_time; i++) {
        arr1 = generate_random_array(max_size, max_value, &real_length);
        arr2 = copy_array(arr1, real_length);
        arr3 = copy_array(arr1, real_length);
//        divide_conquer_sort(arr1, real_length);
        q_sort(arr1, real_length);
        qsort(arr2, real_length , sizeof(int),comp);
        if (!is_equal(arr1, real_length, arr2, real_length)) {
            succeed = false;
            break;
        }
       if (arr1 != NULL) free(arr1); 
       if (arr2 != NULL) free(arr2); 
       if (arr3 != NULL) free(arr3);
        arr1 = NULL; arr2 = NULL; arr3 = NULL;
    }
    printf("%s\n", succeed ? "Nice!" : "Fucking fucked!");
    if (succeed == false) {
        printf("insertsort\n");
        print_array(arr1,real_length) ;
        printf("qsort\n");
        print_array(arr2, real_length);
        printf("raw\n");
        print_array(arr3, real_length);
    }
}